2017-07-20

noip模拟赛2017.7.20

题目名称	产品排序	分球	地图	数页码
提交文件	sort.*	ball.*	map.*	count.*
输入文件	sort.in	ball.in	map.in	count.in
输出文件	sort.out	ball.out	map.out	count.out
时间限制	1s	1s	1s	1s
空间限制	128MB	128MB	128MB	32MB
题目来源	vijos	vijos	模拟题	模拟题

产品排序

题目描述

有一系列产品，给定每个产品的加工时间和冷却成型时间（冷却过程产品之间没有关系，是单独冷却的）。现在你手上有两台机器可以用来加工，你需要安排产品加工的顺序以及去哪台机器加工，使得所有产品都成型的时间最早。机器之间互不相关，可以同时进行工作，一个机器一个时刻只能加工一个产品。

输入格式

第一行一个数 n，表示产品个数，以下 n 行，每行两个数分别表示产品的加工时间 A[i]和冷却时间 B[i]。

输出格式

一个数，表示所有产品成型的最早时间。

数据规模

对于 20%的数据，满足 n<=6;
对于 100%的数据，满足 n,A[i],B[i]<=200。

输入样例

输出样例

题解

对于一个机器的情况，我们贪心处理，按冷却时间降序排序一定是最优的(因为冷却时间长的肯定先加工嘛)
然后考虑两个机器的情况，因为所有产品都是要加工的，所以两个机器加工的总时间一定，那么我们可以动规处理，dp[i][j]表示加工前i件产品，其中第一个机器加工时长为j的时候，最少什么时候加工完成，如此说来，状态转移方程就好写了
如果用第一台机器加工，那么就是

如果用第二台机器加工，那么就是

#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF (1<<30)
using namespace std;
int dp[202][40400];
struct node{
	int t1,t2;
}a[202];
bool cmp(node x,node y){
	return x.t2>y.t2;
}
int sum[202];
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].t1,&a[i].t2);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i].t1;
		for(int ta=0;ta<=sum[i];ta++){
			int tb=sum[i]-ta;
			dp[i][ta]=INF;
			if(ta>=a[i].t1)
				dp[i][ta]=min(dp[i][ta],max(ta+a[i].t2,dp[i-1][ta-a[i].t1]));
			if(tb>=a[i].t1)
				dp[i][ta]=min(dp[i][ta],max(tb+a[i].t2,dp[i-1][ta]));
		}
	}
	int ans=INF;
	for(int ta=0;ta<=sum[n];ta++)
		ans=min(dp[n][ta],ans);
	printf("%d",ans);
}

分球

题目描述

有 N 个标号的球分到 M 个无差别的盒子里，每个盒子至少有一个球，问方案数。

输入格式

多组数据；
每部分一行两个数 N、M。

输出格式

每组数据输出一行，一个数，表示方案数。

数据规模

对于 20%的数据，满足 1<=N，M<=10;
对于 100%的数据，满足 1<=N，M<=100，数组组数<=10。

输入样例

输出样例

样例解释

N=4,M=2
1,234 ；2,134；3,124；4,123；12,34；13,24；14,23

题解

高精度DP，待填坑

地图

题目描述

给定一张地图，定义 X 表示陆地，O 表示海洋。两个格子连通，当且仅当它们共边。一个大陆定义是一个极大的陆地连通块。极大的连通块的定义是不存在一个格子与当前连通块中的某个格子相连但不属于当前连通块。问地图中有几个大陆。

输入格式

第一行两个数 N，M，表示地图的大小，以下 N 行，每行 M 个字母。

输出格式

一个数，表示大陆个数。

数据规模

对于 30%的数据，满足 1<=N，M<=50。
对于 100%的数据，满足 1<=N，M<=1000。

输入样例

5 5
XXXOO
OOXOO
OOOXX
XOOOO
XOXXX

输出样例

题解

简单的搜索

#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF (1<<30)
#define LL long long
using namespace std;
bool mp[2000][2000];
int m,n,ans;
char s[2000];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y){
	mp[x][y]=true;
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(!mp[xx][yy])
			dfs(xx,yy);
	}
}
int main(){
	freopen("map.in","r",stdin);
	freopen("map.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			if(s[j]=='O')
				mp[i][j]=true;		
	}
	for(int i=1;i<=n;i++)
		mp[i][0]=mp[i][m+1]=true;
	for(int j=1;j<=m;j++)
		mp[0][j]=mp[n+1][j]=true;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!mp[i][j]){
				dfs(i,j);
				ans++;
			}
	printf("%d",ans);
}
/*
5 5
XXXOO
OOXOO
OOOXX
XOOOO
XOXXX
*/

数页码

题目描述

一本书的页码是从 1-n 编号的连续整数：1，2，3…，n。请你求出全部页码中所有单个数字的和，例如第 123 页，它的和就是 1+2+3=6。

输入格式

一行为 n(1<=n<=10^9)。

输出格式

一行，代表所有单个数字的和。

输入样例

3456789

输出样例

96342015

题解

可以考虑分位处理，先统计个位上出现的，再算十位…以此类推。但是要注意不要忘了每个位置剩下的，因为由于每个位的数字不相同，所以可能…这个只能意会吧。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int c[10],n;
long long ans;
int Get_Num(int x){
	int rtn=0;
	while(x)
	{
		x/=10;
		rtn++;
	}
	return rtn;
}
int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	scanf("%d",&n);
	int num=Get_Num(n);
	int pow=1;
	for(int j=1;j<=num;j++)
	{
		pow*=10;
		int Pre_Number=n/pow*pow;
		int Bac_Number=n-Pre_Number;
		for(int i=1;i<=9;i++)
			c[i]+=Pre_Number/10;
		int Re_Number=Bac_Number*10/pow;
		for(int i=1;i<Re_Number;i++)
			c[i]+=pow/10;
		c[Re_Number]+=Bac_Number-Re_Number*(pow/10)+1;
	}
	for(int i=1;i<=9;i++)
		ans+=c[i]*i;
	printf("%d\n",ans);
}
/*
3
1 4
3 3
4 1
*/